package com.lzq.leetcode.hoot100;

import com.lzq.leetcode.hoot100.ds.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class s101 {

    public boolean isSymmetric(TreeNode root) {
        // 中遍历
        List<TreeNode> half = new ArrayList<>();
        Deque<TreeNode> dq = new LinkedList<>();

        TreeNode p = root;

        while (true) {
            // 左
            while (p.left != null) {
                dq.addFirst(p);
                p = p.left;
            }

            half.add(p);
            // 中
            p = dq.getFirst();
            if (p == root) {
                break;
            }
            half.add(p);
            // 右
            p = p.right;
        }

        // 判断是否是对称的
        p = root.right;
        int i = half.size() - 1;
        while (p != null || !dq.isEmpty()) {
            // 左
            while (p.left != null) {
                dq.addFirst(p);
                p = p.left;
            }

            if (half.get(i--).val != p.val) {
                return false;
            }
            // 中
            p = dq.getFirst();
            if (p == root) {
                break;
            }
            if (half.get(i--).val != p.val) {
                return false;
            }
            // 右
            p = p.right;
        }

        return true;
    }


}
